#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int inf = 0x3f3f3f3f;
const int N = 2e5+10;

int n,val[N],D[N],d[N],m,p[N],End;
ll f[N];

bool check(int x){
	memset(f,0x3f,sizeof(f));
	for(int i = 1;i <= n;i++)
		if(val[i] >= x) f[i] = 0;
		else if(val[i] == 0) f[i] = 1;
	int st = 1,en = n+1;
	while(en <= End){
//		cout<<en<<st<<endl;
		f[en] = min(f[en],min(f[st] + f[st+1] , min(f[st] + f[st+2] , f[st+1] + f[st+2]))); en++; st += 3;
//		cout<<f[en-1]<<" ";
	}en--;
	int tt = lower_bound(d+1,d+n-m+2,x) - d; if(x <= d[tt]) tt--; tt = n-m-tt;
//cout<<x<<":"<<f[en]<<" "<<tt<<endl;
	return (f[en] <= tt);
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,m = in;
	for(int i = 1;i <= m;i++) D[i] = in,p[i] = in,val[p[i]] = D[i];
	for(int i = 1;i <= n-m;i++) d[i] = in,D[i+m] = d[i];
	End = n / 2 + n; d[n-m+1] = inf;
	sort(D+1,D+n+1); sort(d+1,d+n-m+2);
	int l = 1,r = n,ans = 1;
	while(l <= r){
		int mid = l+r>>1;
		if(check(D[mid])) ans = max(ans,mid),l = mid+1;
		else r = mid-1;
	}//cout<<ans<<endl;
	printf("%d\n",D[ans]);
	return 0;
}
